/***************************************************************************

Copyright (c) Microsoft Corporation. All rights reserved.
This code is licensed under the Visual Studio SDK license terms.
THIS CODE IS PROVIDED *AS IS* WITHOUT WARRANTY OF
ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING ANY
IMPLIED WARRANTIES OF FITNESS FOR A PARTICULAR
PURPOSE, MERCHANTABILITY, OR NON-INFRINGEMENT.

***************************************************************************/

using System;
using System.Diagnostics;
using System.Text;

namespace Babel.ParserGenerator
{
    //HACK...
}

namespace Microsoft.WowAddonStudio.Lua.Parser
{
    /// <summary>
    /// The abstract base class of the Babel Shift/Reduce parser that is generated based on the YACC syntax.
    /// </summary>
    /// <typeparam name="YYSTYPE">The type of the lexical value.</typeparam>
    /// <typeparam name="YYLTYPE">The type of the lexical location.</typeparam>
    public abstract class ShiftReduceParser<YYSTYPE, YYLTYPE> where YYSTYPE : struct
                                                              where YYLTYPE : IMerge<YYLTYPE>
    {
        // Experimental : last yylloc prior to call of yylex()
        private readonly ParserStack<State> state_stack = new ParserStack<State>();
        private int tokensSinceLastError;
        private State current_state;
        private bool recovering;
        private int next;

        protected ParserStack<YYLTYPE> location_stack = new ParserStack<YYLTYPE>();
        protected ParserStack<YYSTYPE> value_stack = new ParserStack<YYSTYPE>();

        protected Rule[] rules;
        protected State[] states;

        protected YYLTYPE lastL;
        protected YYLTYPE yyloc;
        protected YYSTYPE yyval;

        protected int eofToken;
        protected int errToken;

        protected string[] nonTerminals;

        public AScanner<YYSTYPE, YYLTYPE> Scanner { get; set; }
        public bool Tracing { get; set; }

        protected abstract void Initialize();

        /// <summary>
        /// Parses the source.
        /// </summary>
        /// <returns>True, if the parse was successful; False otherwise.</returns>
        public virtual bool Parse()
        {
            Initialize(); // allow derived classes to instantiate rules, states and nonTerminals

            next = 0;
            current_state = states[0];

            state_stack.Push(current_state);
            value_stack.Push(yyval);
            location_stack.Push(yyloc);

            try
            {

                while (true)
                {
                    if (Tracing)
                        Trace.WriteLine("Entering state " + current_state.num);

                    int action = current_state.defaultAction;

                    if (current_state.parser_table != null)
                    {
                        if (next == 0)
                        {
                            if (Tracing)
                                Trace.Write("Reading a token: ");

                            // We save the last token span, so that the location span
                            // of production right hand sides that begin or end with a
                            // nullable production will be correct.
                            lastL = Scanner.yylloc;
                            next = Scanner.yylex();
                        }

                        if (Tracing)
                            Trace.WriteLine("Next token is " + TerminalToString(next));

                        if (current_state.parser_table.ContainsKey(next))
                            action = current_state.parser_table[next];
                    }

                    if (action > 0) // shift
                        Shift(action);
                    else if (action < 0) // reduce
                    {
                        Reduce(-action);

                        if (action == -1) // accept
                            return true;
                    }
                    else if (action == 0) // error
                    {
                        if (!ErrorRecovery())
                            return false;
                    }
                }
            }
            catch
            {
                return false;
            }
        }

        /// <summary>
        /// Shifts the specified state_nr.
        /// </summary>
        /// <param name="state_nr">The state_nr.</param>
        protected void Shift(int state_nr)
        {
            if (Tracing)
                Trace.Write(String.Format("Shifting token {0}, ", TerminalToString(next)));

            current_state = states[state_nr];

            value_stack.Push(Scanner.yylval);
            state_stack.Push(current_state);
            location_stack.Push(Scanner.yylloc);

            if (recovering)
            {
                if (next != errToken)
                    tokensSinceLastError++;

                if (tokensSinceLastError > 5)
                    recovering = false;
            }

            if (next != eofToken)
                next = 0;
        }

        /// <summary>
        /// Reduces the specified rule_nr.
        /// </summary>
        /// <param name="rule_nr">The rule_nr.</param>
        protected void Reduce(int rule_nr)
        {
            if (Tracing)
                DisplayRule(rule_nr);

            Rule rule = rules[rule_nr];
            //
            //  Default action "$$ = $1" for unit productions.
            //
            if (rule.rhs.Length == 1)
                yyval = value_stack.Top(); // default action: $$ = $1;
            else
                yyval = new YYSTYPE();
            //
            //  Default action "@$ = @1.Merge(@N)" for location info.
            //
            if (rule.rhs.Length == 1)
                yyloc = location_stack.Top();
            else if (rule.rhs.Length == 0)
                // The location span for an empty production will start with the
                // beginning of the next lexeme, and end with the finish of the
                // previous lexeme.  This gives the correct behaviour when this
                // nonsence value is used in later Merge operations.
                yyloc = (Scanner.yylloc != null ? Scanner.yylloc.Merge(lastL) : default(YYLTYPE));
            else
            {
                YYLTYPE at1 = location_stack.array[location_stack.top - rule.rhs.Length];
                YYLTYPE atN = location_stack.Top();
                if (at1 != null && atN != null)
                    yyloc = at1.Merge(atN);
            }

            DoBeforeAction(rule_nr);
            DoAction(rule_nr);
            DoAfterAction(rule_nr);

            for (int i = 0; i < rule.rhs.Length; i++)
            {
                state_stack.Pop();
                value_stack.Pop();
                location_stack.Pop();
            }

            if (Tracing)
                DisplayStack();

            current_state = state_stack.Top();

            if (current_state.Goto.ContainsKey(rule.lhs))
                current_state = states[current_state.Goto[rule.lhs]];

            state_stack.Push(current_state);
            value_stack.Push(yyval);
            location_stack.Push(yyloc);
        }

        protected virtual void DoBeforeAction(int action_nr)
        {
        }

        protected abstract void DoAction(int action_nr);

        protected virtual void DoAfterAction(int action_nr)
        {
        }

        /// <summary>
        /// Errors the recovery.
        /// </summary>
        /// <returns></returns>
        public bool ErrorRecovery()
        {
            bool discard;

            if (!recovering) // if not recovering from previous error
                ReportError();

            if (!FindErrorRecoveryState())
                return false;
            //
            //  The interim fix for the "looping in error recovery"
            //  artifact involved moving the setting of the recovering 
            //  bool until after invalid tokens have been discarded.
            //
            ShiftErrorToken();
            discard = DiscardInvalidTokens();
            recovering = true;
            tokensSinceLastError = 0;
            return discard;
        }

        /// <summary>
        /// Reports the error.
        /// </summary>
        public void ReportError()
        {
            var errorMsg = new StringBuilder();
            errorMsg.AppendFormat("syntax error, unexpected {0}", TerminalToString(next));

            if (current_state.parser_table.Count < 7)
            {
                bool first = true;
                foreach (int terminal in current_state.parser_table.Keys)
                {
                    if (first)
                        errorMsg.Append(", expecting ");
                    else
                        errorMsg.Append(", or ");

                    errorMsg.Append(TerminalToString(terminal));
                    first = false;
                }
            }

            Scanner.yyerror(errorMsg.ToString());

            if (Tracing)
                Trace.WriteLine(errorMsg.ToString());
        }

        /// <summary>
        /// Shifts the error token.
        /// </summary>
        public void ShiftErrorToken()
        {
            int old_next = next;
            next = errToken;

            if (Tracing)
                Trace.WriteLine(String.Format("Shifting error in state {0}", current_state.num));

            Shift(current_state.parser_table[next]);

            if (Tracing)
                Trace.WriteLine("Entering state " + current_state.num);

            next = old_next;
        }

        /// <summary>
        /// Finds the state of the error recovery.
        /// </summary>
        /// <returns></returns>
        public bool FindErrorRecoveryState()
        {
            while (true) // pop states until one found that accepts error token
            {
                if (current_state.parser_table != null && current_state.parser_table.ContainsKey(errToken) &&
                    current_state.parser_table[errToken] > 0) // shift
                    return true;

                if (Tracing)
                    Trace.WriteLine("Error: popping state " + state_stack.Top().num);

                state_stack.Pop();
                value_stack.Pop();
                location_stack.Pop();

                if (Tracing)
                    DisplayStack();

                if (state_stack.Count == 0)
                {
                    if (Tracing)
                        Trace.Write("Aborting: didn't find a state that accepts error token");

                    return false;
                }
                else
                    current_state = state_stack.Top();
            }
        }

        /// <summary>
        /// Discards the invalid tokens.
        /// </summary>
        /// <returns></returns>
        public bool DiscardInvalidTokens()
        {
            int action = current_state.defaultAction;

            if (current_state.parser_table != null)
            {
                // Discard tokens until find one that works ...
                while (true)
                {
                    if (next == 0)
                    {
                        if (Tracing)
                            Trace.Write("Reading a token: ");

                        next = Scanner.yylex();
                    }

                    if (Tracing)
                        Trace.WriteLine("Next token is " + TerminalToString(next));

                    if (next == eofToken)
                        return false;

                    if (current_state.parser_table.ContainsKey(next))
                        action = current_state.parser_table[next];

                    if (action != 0)
                        return true;
                    else
                    {
                        if (Tracing)
                            Trace.WriteLine("Error: Discarding " + TerminalToString(next));
                        next = 0;
                    }
                }
            }
            else if (recovering && tokensSinceLastError == 0)
            {
                // 
                //  Boolean recovering is not set until after the first
                //  error token has been shifted.  Thus if we get back 
                //  here with recovering set and no tokens read we are
                //  looping on the same error recovery action.  This 
                //  happens if current_state.parser_table is null because
                //  the state has an LR(0) reduction, but not all
                //  lookahead tokens are valid.  This only occurs for
                //  error productions that *end* on "error".
                //
                //  This action discards tokens one at a time until
                //  the looping stops.  Another attack would be to always
                //  use the LALR(1) table if a production ends on "error"
                //
                if (Tracing)
                    Trace.WriteLine("Error: panic discard of " + TerminalToString(next));
                next = 0;
                return true;
            }
            else
                return true;
        }

        /// <summary>
        /// Yyclearins this instance.
        /// </summary>
        protected void yyclearin() // experimental in this version.
        {
            next = 0;
        }

        /// <summary>
        /// Yyerroks this instance.
        /// </summary>
        protected void yyerrok()
        {
            recovering = false;
        }

        /// <summary>
        /// Adds the state.
        /// </summary>
        /// <param name="statenr">The statenr.</param>
        /// <param name="state">The state.</param>
        protected void AddState(int statenr, State state)
        {
            states[statenr] = state;
            state.num = statenr;
        }

        /// <summary>
        /// Displays the stack.
        /// </summary>
        private void DisplayStack()
        {
            Trace.Write("State now");
            for (int i = 0; i < state_stack.top; i++)
            {
                Trace.Write(" " + state_stack.array[i].num);
            }
            Trace.WriteLine(String.Empty);
        }

        /// <summary>
        /// Displays the rule.
        /// </summary>
        /// <param name="rule_nr">The rule_nr.</param>
        private void DisplayRule(int rule_nr)
        {
            Trace.Write(String.Format("Reducing stack by rule {0}, ", rule_nr));
            DisplayProduction(rules[rule_nr]);
        }

        /// <summary>
        /// Displays the production.
        /// </summary>
        /// <param name="rule">The rule.</param>
        private void DisplayProduction(Rule rule)
        {
            if (rule.rhs.Length == 0)
                Trace.Write("/* empty */ ");
            else
            {
                foreach (int symbol in rule.rhs)
                    Trace.Write(SymbolToString(symbol) + " ");
            }

            Trace.WriteLine("-> " + SymbolToString(rule.lhs));
        }

        /// <summary>
        /// Terminals to string.
        /// </summary>
        /// <param name="terminal">The terminal.</param>
        /// <returns></returns>
        protected abstract string TerminalToString(int terminal);

        /// <summary>
        /// Symbols to string.
        /// </summary>
        /// <param name="symbol">The symbol.</param>
        /// <returns></returns>
        private string SymbolToString(int symbol)
        {
            if (symbol < 0)
                return nonTerminals[-symbol];
            else
                return TerminalToString(symbol);
        }

        /// <summary>
        /// Chars to string.
        /// </summary>
        /// <param name="ch">The ch.</param>
        /// <returns></returns>
        protected string CharToString(char ch)
        {
            switch (ch)
            {
                case '\a':
                    return @"'\a'";
                case '\b':
                    return @"'\b'";
                case '\f':
                    return @"'\f'";
                case '\n':
                    return @"'\n'";
                case '\r':
                    return @"'\r'";
                case '\t':
                    return @"'\t'";
                case '\v':
                    return @"'\v'";
                case '\0':
                    return @"'\0'";
                default:
                    return string.Format("'{0}'", ch);
            }
        }
    }
}